HW#3 --- last modified February 07 2019 04:29:43..

Solution set.

Due date: Mar 17

Files to be submitted:
  Hw3.zip

Purpose: Experiment with quicksort and radix sort variants

The main course outcomes covered by this assignment are:

LO4 -- Use advanced sorting techniques (radix sort, heapsort, mergesort, quicksort).

Specification:

This project consists in the development of four programs and a write-up of experiments conducted with these programs. The first program is a random string generator. The grader will compile this program as the command line using:

javac RandomStringGenerator.java

The program will then be run with a line like:

java RandomStringGenerator prob num_strings

For example,

java RandomStringGenerator .1 5

The prob value is used to control the length of the string, the num_strings value controls the number of strings generated. To generate a string, your program should choose uniformly at random a character amongst a,b,c,...,z. This is the first character of the string. Then it should choose a float value uniformly at random between 0 and 1. If this is less than prob (in this example, 0.1) it should continue to build the string, otherwise, it should stop building the string and output it to stdout (one string/line). If it continues building the string it repeats the process just described: It picks a random character amongst a,b,c,...,z appends it to the string, then picks a random float between 0 and 1, etc. Example output for the above statement might be:

f
t
yr
q
dar

We could of course use a command-line redirect to send the output to a file. The second program you will write for this homework is FileQuickSort.java. It will be compiled from the command line with a line like:

javac FileQuickSort.java

and it will be run with a line like:

java FileQuickSort filename.txt pivot_pos

Here filename.txt is an arbitrary name of a file containing strings over the alphabet a-z, one string per line. So if blah.txt were a file containing:

adsgfa
hfgfh
jfgiouterhd
fhgj
slkjfjhkgfdsf

I could run FileQuickSort on it using:

java FileQuickSort blah.txt 3

FileQuickSort should implement a variant of quicksort with pivots chosen according to pivot_pos. That is, whenever the quicksort makes a recursive call to quicksort a subarray `A`, `p`, `r`, it chooses as the pivot `min(p+text(pivot_pos), r)`. The documentation at the start of the file should clearly indicate the line number where your code for this lives. The output of FileQuickSort is the same lines input but in sorted order, followed by a time in milliseconds to do the sorting. For the example above,

adsgfa
fhgj
hfgfh
jfgiouterhd
slkjfjhkgfdsf
123 milliseconds

The next program I want you to write is FileQuickInsertSort.java. Again, it will be compile with a line like:

javac FileQuickInsertSort.java

and run with a line like:

java FileQuickInsertSort filename.txt insert_threshold

For example,

java FileQuickInsertSort blah.txt 5

This variant on quicksort uses a randomly chosen pivot from amongst the elements of the sub-array that are being sorted, unless the subarray to be sorted has size less than insert_threshold, in which case, rather than do quicksort on the subarray, it just runs insertion sort on it. The comments on the top of this file should clearly indicate where to look for this modification. The output of this program is again the sorted strings each on a line followed by the run-time.

The last program I want you to implement is FileModifiedRadixSort.java. It will be compile with a line like:

javac FileModifiedRadixSort.java

and run with a line like:

java FileModifiedRadixSort filename.txt

For example,

java FileModifiedRadixSort blah.txt

This program also takes the strings in filename.txt or blah.txt and outputs them in sorted order followed by the time in milliseconds. To do the sorting it should make an initial pass through the strings and find the longest string. It should then pretend all the strings have this length and do radix sort. Sorting thus would proceed from the last column to the first column. If a string does not have a column `i` because it is too short, we pretend that it has a value @ for that column and that @ is earlier in the alphabet than the letter a. When we write the final output we write the original strings (no @ signs).

Once you have your four programs I want you to do some experiments with them. I would like to use RandomStringGenerator to generate 10 files where the prob takes on the different values 0.9, 0.91, 0.92, ... 0.99 and the number of strings to sort is from 5000. Then I want you to generate 10 more files where the prob is 0.95 and the number of strings to sorts is 1000, 2000, 3000, ..., 10000. For FileQuickSort I want you to choose the pivot position to be 2, for FileQuickInsertSort I want you to choose the insert_threshold to be 7. Then I want you to run your three sorters using these parameters on each of these test files. I would like you to plot your results on graphs and write a page report summarizing what you found out. Put your report with graphs in a file Hw3.pdf in your submitted ZIP file.

Point Breakdown